package cn.cxq.learning.tree;

/**
 * 顺序存储二叉树，正如他的名字中可以得到的信息，他是顺序存储的，这不难让我们想象到数组，
 * 数组有的特性他都有，树有的特性他也有，所以他可以实现不需要左右节点的指针，通过简单的逻辑运算就可以找到每个节点的左右节点。
 */
public class SequentialStorageBinaryTree {

    private SequentialNode[] nodes;

    public SequentialStorageBinaryTree(SequentialNode[] nodes) {
        this.nodes = nodes;
    }

    public void preorderTraversal() {
        if (nodes.length == 0) System.out.println("顺序存储二叉树为空~~~");
        else preorderTraversalItem(0);
    }

    public void preorderTraversalItem(int index) {

        System.out.println(this.nodes[index]);
        if (2 * index + 1 < this.nodes.length) preorderTraversalItem(2 * index + 1);
        if (2 * index + 2 < this.nodes.length) preorderTraversalItem(2 * index + 2);
    }

    public void inorderTraversal() {
        if (nodes.length == 0) System.out.println("顺序存储二叉树为空~~~");
        else inorderTraversalItem(0);
    }

    public void inorderTraversalItem(int index) {

        if (2 * index + 1 < this.nodes.length) inorderTraversalItem(2 * index + 1);
        System.out.println(this.nodes[index]);
        if (2 * index + 2 < this.nodes.length) inorderTraversalItem(2 * index + 2);
    }

    public void postorderTraversal() {
        if (nodes.length == 0) System.out.println("顺序存储二叉树为空~~~");
        else postorderTraversalItem(0);
    }

    public void postorderTraversalItem(int index) {

        if (2 * index + 1 < this.nodes.length) postorderTraversalItem(2 * index + 1);
        if (2 * index + 2 < this.nodes.length) postorderTraversalItem(2 * index + 2);
        System.out.println(this.nodes[index]);
    }
}

class SequentialNode {

    private int no;
    private String msg;

    public SequentialNode(int no, String msg) {
        this.no = no;
        this.msg = msg;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getMsg() {
        return msg;
    }

    public void setMsg(String msg) {
        this.msg = msg;
    }

    @Override
    public String toString() {
        return "SequentialNode{" +
                "no=" + no +
                ", msg='" + msg + '\'' +
                '}';
    }
}
